#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    string addBinary(string a, string b)
    {
        string ans;
        // 翻转两个字符串,从低位到高位计算
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size());
        int carry = 0;  // 进位
        for (size_t i = 0; i < n; ++i) {
            // 从低位到高位把对应的位相加
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            // 相加后的结果添加到要返回的字符串中
            ans.push_back((carry % 2) ? '1' : '0');
            // 判断是否需要进位
            carry /= 2;
        }
        // 如果要进位,最高位补 1
        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

int main()
{
    cout << "Hello World!" << endl;
    return 0;
}
